package com.zz.array;

/**
 * @author 张哲
 * @email a252013135@163.com
 * @date 2024/9/12 16:19
 * <p>
 * 把⼀个数组最开始的若⼲个元素搬到数组的末尾，我们称之为数组的旋转。
 * 输⼊⼀个⾮递减排序的数组的⼀个旋转，输出旋转数组的最⼩元素。
 * 例如数组 {3,4,5,1,2} 为 {1,2,3,4,5} 的⼀个旋转，该数组的最⼩值为 1。
 * NOTE：给出的所有元素都⼤于 0，若数组⼤⼩为 0，请返回 0。
 */
public class Offer11 {
    /**
     * 暴力破解
     *
     * @param array
     * @return
     */
    public int minNumberInRotateArray1(int[] array) {
        if (array == null || array.length == 0) {
            return 0;
        }
        if (array.length == 1) {
            return array[0];
        }
        for (int i = 1; i < array.length; i++) {
            if (array[i] < array[i - 1]) {
                return array[i];
            }
        }
        return 0;
    }

    /**
     * 二分法
     *
     * @param array
     * @return
     */
    public int minNumberInRotateArray2(int[] array) {
        if (array == null || array.length == 0) {
            return 0;
        }
        if (array.length == 1) {
            return array[0];
        }
        int left = 0;
        int right = array.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (array[mid] < array[right]) {
                // 证明目前在后一部分，而目标值在左侧
                right = mid;
            } else {
                // 证明目前在前一部分，而目标值在后一部分第一个
                left = mid + 1;
            }
        }
        return array[left];
    }
}
